namespace map2D {
	/*
	 * A* 寻路算法
	 * 
	 * @author Dingo
	 * @version 1.0
	 * @date 070831
	 */
	export class AStar implements IListener{
		public testLay:GYSprite;

		/**是否允许寻路时斜线走动*/public canDiaonal:boolean;
		//垂直或水平移动一格的代价
		private COST_STRAIGHT:number = 10;
		//斜向移动一格的代价
		private COST_DIAGONAL:number = 14;
		//逆向偏离目标的代价
		private COST_INSERVE:number = 80;
		//起始节点ANode
		private _ndStart:ANode;
		//目标节点ANode
		private _ndEnd:ANode;
		//当前节点ANode
		private _ndCurrent:ANode;
		//最大寻路步数限制
		private _nMaxTry:number;
		//尝试次数计数器
		private _nCrtTry:number;
		//开放表，元素为ANode类型
		private _aOpenList:ANode[];
		//关闭表，元素为ANode类型
		private _aCloseList:ANode[];
		//尝试表，元素为ANode类型
		private _aTryList:ANode[];
		//八个方向数组，从节点正上方开始，顺时针排列
		private static aDir:any[] = [[0,-1],[1,-1],[1,0],[1,1],[0,1],[-1,1],[-1,0],[-1,-1]];
		//地图节点数组
		// public aNodeMap:number[] = [];
		//地图宽度(格子列数)
		private _mapWidth:number;
		//地图宽度(格子行数)
		private _mapHeight:number;
		//记录节点在aOpenList数组的位置
		// private _num:number;
		//路径数组
		// public aPath:any[];
		//是否找到路径
		// public bPathFind:boolean;
		//场景对象
		private _scene:IScene;
		private _listenId:number =-1;
		private _debug:boolean;		
		public static starTry:number = 300;//astar步数300
		//构造函数
		public constructor(scene:IScene,debug:boolean = false) {
			let s = this;
			s._nMaxTry = 600;
			s._nCrtTry = 0;
			s._aOpenList = [];
			s._aCloseList = [];			
			s._mapWidth = scene.mapGridCol;//amap[0].length;
			s._mapHeight = scene.mapGridRow;//amap.length;
			s._scene = scene;
			s.canDiaonal = true;
			s._aTryList = [];	
			s._debug = debug;		
			// s.aNodeMap = amap;
		}		
		//添加到open表
		// public addFirstOpen():void{
		// 	let s = this;
		// 	s.aOpenList.push(s.ndStart);
		// }
		/**取得指定点周围可通过的点，从正上方开始*/
		private getRound(closeList:ANode[], ndStart:ANode,ndCurrent:ANode,apos:number[],endFlag:number=-1,canPassFlag:number=1):number[][]{
			let s = this;
			var arr:number[][] = [];			
			for(var i:number=0;i<AStar.aDir.length;i++){
				var xp = apos[0] + AStar.aDir[i][0];
				var yp = apos[1] + AStar.aDir[i][1];
				if(endFlag != -1 && s._scene.canGridPass(xp,yp,endFlag))//遭遇结束格子
					return null;
				if(s.isStart(xp,yp,ndStart) || !s.isPass(xp,yp,canPassFlag) || s.isCorner(xp,yp,ndCurrent) || s.isInList(closeList,xp,yp) > -1)
					continue
				arr.push([xp,yp]);				
			}			
			return arr;
		}		
		// //是否超出地图范围
		// private isOutRange(apos:any[]):boolean{
		// 	let s = this;
		// 	if(apos[0]<0 || apos[0] >= s.mapwidth || apos[1] < 0 || apos[1]>= s.mapheight)
		// 		return true;
		// 	return false;
		// }		
		//是否是起点
		private isStart(col:number,row:number,ndStart:ANode):boolean{ 
			let s =this;
    		if(col == ndStart.pos[0] && row == ndStart.pos[1])
       			return true;
    		return false;
		}
		// //是否可以通过		
		private isPass(col:number,row:number, canPassFlag:number=Barrier.LAND):boolean{ 
			let s = this;
			// if(s.isOutRange(apos)){
			// 	return false;
			// }else{	
			// 	return (s.aNodeMap[apos[1]][apos[0]]>0?false:true);
			// }
			return s._scene.canGridPass(col,row, canPassFlag) > 0;
		}				
		//是否不可通行的拐角
		private isCorner(col:number,row:number,ndCurrent:ANode):boolean{
			let s = this;			
			if(!s.canDiaonal)return true;
			if(s.isPass(col,row)){
				if(col > ndCurrent.pos[0]){
					if(row > ndCurrent.pos[1]){
						// if(!s.canDiaonal)return true;
						if(!s.isPass(col - 1,row) || !s.isPass(col,row - 1))
							return true;
					}
					else if(row < ndCurrent.pos[1]){
						// if(!s.canDiaonal)return true;
						if(!s.isPass(col - 1,row) || !s.isPass(col,row + 1))
							return true;
					}
				}
				else if(col < ndCurrent.pos[0]){
					if(row > ndCurrent.pos[1]){
						// if(!s.canDiaonal)return true;
						if(!s.isPass(col + 1,row) || !s.isPass(col,row - 1))
							return true;
					}
					else if(row < ndCurrent.pos[1]){
						// if(!s.canDiaonal)return true;
						if(!s.isPass(col + 1,row) || !s.isPass(col,row + 1))
							return true;
					}
				}
				return false;
			}
			return true;
		}
		/**是否在列表中*/
		private isInList(list:ANode[],col:number,row:number):number{
			let s = this;    		
			var id = row * s._mapWidth + col;
    		for(var i=0;i<list.length;i++){
        		if(list[i].id == id){          			
					return i;					
				}
   			}    		
			return -1;
		}
		//是否在开启列表中
		//获得传入参数在aOpenlist数组的位置，如不存在返回false，存在为true，位置索引保存到变量num中。
		// private isInOpen(apos:number[]):number{
		// 	let s = this;    		
		// 	var id = apos[1] * s._mapWidth + apos[0];
    	// 	for(var i=0;i<s._aOpenList.length;i++){
        // 		if(s._aOpenList[i].id == id){          			
		// 			return i;					
		// 		}
   		// 	}    		
		// 	return -1;
		// }
		// //是否在关闭列表中
		// private isInClose(col:number,row:number):boolean{
		// 	let s =this;
		// 	var bool:boolean = false;
		// 	var id = row * s._mapWidth + col;
    	// 	for(var i=0;i<s._aCloseList.length;i++){
        // 		if(s._aCloseList[i].id == id){
        //     		bool=true;
		// 			break;
		// 		}
    	// 	}
    	// 	return bool;
		// }
		//取得F值，参数为某一节点周围的节点
		private getF(aOpenList:ANode[], ndStart:ANode, ndCurrent:ANode, ndEnd:ANode, around:number[][]):void{ 
		    //f,综合的距离值；
			//h,给定节点到目标点的距离值；
			//g,起点到给定节点的距离值
			let f:number,g:number,h:number;
			let s =this;			
			let apos:number[];
			for(var i:number = 0;i < around.length;i++){					
				apos = around[i];					
				//是否与起点在同一直线上
				if(apos[0] == ndStart.pos[0] || apos[1] == ndStart.pos[1]){
					g = ndCurrent.G + s.COST_STRAIGHT;
				}else{
					g = ndCurrent.G + s.COST_DIAGONAL;
				}
				//如果当前点已存在aOpenlist数组中
				let ind:number = s.isInList(aOpenList, apos[0], apos[1]);
				if(ind > -1){
					var opos:ANode = aOpenList[ind];
					//如果当前点G值更小，更改父节点
					if(g<opos.G){
						opos.F = g + opos.H;
						opos.G = g;
						opos.pid = ndCurrent.id;
					}else{
						g = opos.G;
					}
				}
				//否则将当前点添加到aOpenList数组
				else{
					h = s.calculateH(ndCurrent.pos,apos,ndEnd.pos);//(Math.abs(s._ndEnd.pos[0] - apos[0]) + Math.abs(s._ndEnd.pos[1] - apos[1])) * s.COST_STRAIGHT;//估值
					f= g + h;
					var newnode:ANode = ANode.createANode(apos,apos[1] * s._mapWidth + apos[0],0, ndCurrent.id);//new ANode(apos,apos[1] * s.mapWidth + apos[0],0,s.ndCurrent.id);
					newnode.F = f;
					newnode.G = g;
					newnode.H = h;
					aOpenList.push(newnode);
				}			
			}
		}
		//估值
		private calculateH(curPos:number[],nextPos:number[],endPos:number[]):number		
		{
			let s = this;
			let dx:number,dy:number,costAdd:number=0;
			dx = endPos[0] - nextPos[0];			
			dy = endPos[1] - nextPos[1];			
			if(curPos[0] < endPos[0] && nextPos[0] < curPos[0])
			{
				costAdd += s.COST_INSERVE * (endPos[0] - curPos[0]);
			}
			else if(curPos[0] > endPos[0] && nextPos[0] > curPos[0])
			{
				costAdd += s.COST_INSERVE * (curPos[0] - endPos[0]);
			}
			if(curPos[1] < endPos[1] && nextPos[1] < curPos[1])
			{
				costAdd += s.COST_INSERVE * (endPos[1] - curPos[1]);
			}
			else if(curPos[1] > endPos[1] && nextPos[1] > curPos[1])
			{
				costAdd += s.COST_INSERVE * (curPos[1] - endPos[1]);
			}
			if(dx < 0)dx  = -dx;
			if(dy < 0)dy  = -dy;
			return (dx + dy) * s.COST_STRAIGHT + costAdd;//(Math.abs(endPos[0] - nextPos[0]) + Math.abs(endPos[1] - nextPos[1])) * s.COST_STRAIGHT
		}
		private sortF(a:any,b:any):number
		{
			return a.F > b.F?-1:1;
		}
		/**量子搜索路径
		 * @param startCol 起始列索引
		 * @param startRow 起始行索引
		 * @param endCol 结束列索引
		 * @param endRow 结束行索引
		 * @param trackArr 寻路返回的结果数组，不传则创建一个新数组，默认null	 
		 * @param nMaxTry 最大寻路步数限制，默认0 使用系统默认的步数
		 * @param endFlag 结束标志 默认-1，不检测，如果大于0，则检测遍历的格子标志是否符合，符合则直接返回当前路径
		 * @param canPassFlag 寻路中可通行的格子标志，默认Barrier.LAND
		 * @param threadId 线程id，参考ThreadID常量，默认-1，自动产生一个不重复的id(相同id的线程重复执行会覆盖之前的执行)
		 * @param route 指定路线，默认null，不指定，如果指定路线则寻路过程变成从起点寻路到路线的起点，然后到路线的终点寻路到目标终点
		 * @return 如果寻路成功，返回number[][] [[索引x，索引y]……]，失败返回null
		 * */	
		public runDoSearchThread(callBack:(thread:ghost.Thread)=>void,startCol:number,startRow:number,endCol:number,endRow:number,trackArr:number[][]=null,nMaxTry:number=0,endFlag:number=-1,canPassFlag:number=Barrier.LAND,threadId:number=-1,route:number[]=null):ghost.Thread
		{			
			let s = this;
			let movePath:number[][];
			movePath = s.doSearch(startCol,startRow,endCol,endRow,trackArr,AStar.starTry,endFlag,canPassFlag);
			if(movePath && movePath.length > 0)
			{
				let i:number;
				let newPath:number[][] = [];
				let stInd:number,endInd:number;
				let aCol:number,aRow:number,bCol:number,bRow:number,r:number;
				let size:number;
				// let sizeR:number,agl:number,agl2:number,agl3:number;
				let flag:boolean;
				if(movePath.length > 8)
				{
					// sizeR = Math.PI*32;
					size = s._scene.gridSize;
					stInd = movePath.length - 1;
					endInd = 0;
					newPath.unshift(movePath[stInd]);
					while(1)
					{
						if(stInd - endInd > 2)
						{
							aCol = movePath[stInd][0];
							aRow = movePath[stInd][1];
							bCol = movePath[endInd][0];
							bRow = movePath[endInd][1]; 
							flag = s._scene.canLinePass(aCol*size,aRow*size,bCol*size,bRow*size);
							// if(!flag && endInd != 0)//非终点格子，如果失败，我们尝试偏移一下
							// {
							// 	r = PositionUtil.calculateDistance(aCol,aRow,bCol,bRow);
							// 	agl2 = PositionUtil.calculateAngle(aCol,aRow,bCol,bRow);
							// 	agl = sizeR / r;								
							// 	agl3 = agl + agl2;
							// 	bCol = Math.cos(agl3)*r|0;
							// 	bRow = Math.sin(agl3)*r|0;
							// 	flag = s._scene.canLinePass(aCol*size,aRow*size,bCol*size,bRow*size);
							// 	if(!flag)
							// 	{
							// 		agl3 = agl - agl2;
							// 		bCol = Math.cos(agl3)*r|0;
							// 		bRow = Math.sin(agl3)*r|0;
							// 		flag = s._scene.canLinePass(aCol*size,aRow*size,bCol*size,bRow*size);
							// 	}
							// }
							if(flag)
							{							
								newPath.unshift(movePath[endInd]);
								stInd = endInd;
								endInd = 0;
								if(stInd == endInd)
									break;
							}
							else
							{
								endInd = (endInd + stInd)/2|0;
								continue;
							}
						}
						else
						{							
							for(i=stInd-1;i>=endInd;--i)
							{
								newPath.unshift(movePath[i]);
							}
							stInd = endInd;
							endInd = 0;
							if(stInd == endInd)
								break;
						}
					}
					movePath = newPath;
				}
				
				let thread:ghost.Thread = ghost.Thread.runThread(threadId, s.doSearch_Thread, s, [startCol,startRow,endCol,endRow,trackArr,nMaxTry,endFlag,canPassFlag,route], callBack, s, false);
				thread.excEnd(movePath);
				return thread;
			}
			if(route)
				nMaxTry += (nMaxTry>0?nMaxTry:s._nMaxTry) + (route.length/2|0);
			return ghost.Thread.runThread(threadId, s.doSearch_Thread, s, [startCol,startRow,endCol,endRow,trackArr,nMaxTry,endFlag,canPassFlag,route], callBack, s); 	
		}
			
		private doSearch_Thread(startCol:number,startRow:number,endCol:number,endRow:number,trackArr:number[][]=null,nMaxTry:number=0,endFlag:number=-1,canPassFlag:number=Barrier.LAND, route:number[]=null):number[][]{
			let s = this;
			// let apath:number[][],apos:number[][];					
			// apath = trackArr;
			let thread:ghost.Thread;
			let varObj:any;
			let abort:boolean;
			//从参数列表最后一个取出线程对象
			thread = arguments[arguments.length - 1];
			//初始化定义线程函数变量
			if(!thread.inited)
			{
				thread.init({        
					apath:trackArr,
					tempPath:[],
					aOpenList:[],
					aTryList:[],
					aCloseList:[],
					gridSize:s._scene.gridSize,
					ndCurrent:null,
					ndEnd:null,
					ndStart:null,
					nCrtTry:0			
				});
				varObj = thread.varObj;							
				varObj.ndCurrent = varObj.ndStart = ANode.createANode([startCol,startRow],startCol + startRow*s._mapWidth);
				if(route && route.length > 3)
				{					
					let endCol2:number,endRow2:number;
					endCol2 = route.shift()/varObj.gridSize|0;
					endRow2 = route.shift()/varObj.gridSize|0;
					varObj.ndEnd = ANode.createANode([endCol2,endRow2],endCol2 + endRow2*s._mapWidth);
				}					
				else
					varObj.ndEnd = ANode.createANode([endCol,endRow],endCol + endRow*s._mapWidth);
				varObj.aOpenList.push(varObj.ndStart.clone());
			}			
			else
				varObj = thread.varObj;
			
			if(!nMaxTry) nMaxTry = s._nMaxTry;
			while(varObj.aOpenList.length){
				varObj.nCrtTry ++ ;
				//如果超出寻路步数限制
				if(varObj.nCrtTry > nMaxTry){						
					// thread.excEnd(varObj.apath);
					break;
				}
				varObj.aTryList.push(varObj.ndCurrent);
				varObj.apos = s.getRound(varObj.aCloseList, varObj.ndStart,varObj.ndCurrent,varObj.ndCurrent.pos, endFlag, canPassFlag);
				if(varObj.apos == null)
				{
					// varObj.apath = s.getPath(varObj.apath, varObj.aCloseList, varObj.ndStart.id);					
					// varObj.ndStart = varObj.ndCurrent;
					// varObj.apath = varObj.apath.length > 0?varObj.apath:null;
					// if(varObj.apath && varObj.apath.length > 0 && varObj.tempPath && varObj.tempPath.length > 0)
					// 	varObj.apath = varObj.apath.concat(varObj.tempPath);
					break;
				}

				s.getF(varObj.aOpenList, varObj.ndStart, varObj.ndCurrent, varObj.ndEnd, varObj.apos);
				//按照F值由大到小的顺序排列开启列表
				varObj.aOpenList.sort(s.sortF);
				//将开启列表最后一位元素列入关闭列表
				var lastNode:ANode = varObj.aOpenList[varObj.aOpenList.length - 1];
				varObj.aCloseList.push(lastNode);				
				varObj.ndCurrent = lastNode;
				if(varObj.aOpenList.length>1)
					varObj.aOpenList.pop();
				//如果当前节点是目标节点，路径找到，返回true
				if(varObj.ndCurrent.id == varObj.ndEnd.id){
					if(route && route.length > 0)
					{						
						//首段路线装入
						varObj.tempPath = s.getPath(varObj.tempPath, varObj.aCloseList, varObj.ndStart.id);
						//装入中间段的路线
						let i:number,len:number,j:number,len2:number,col:number,row:number;
						let x:number,y:number,lx:number,ly:number;
						let lastPt:Laya.Point, pt:Laya.Point;
						len = route.length - 2;
						for(i=0;i<len;i+=2)
						{
							lx = x;
							ly = y;
							x = route[i];
							y = route[i+1];
							if(i > 0)
							{
								lastPt = null;
								len2 = ghost.PositionUtil.calculateDistance(x,y,lx,ly);
								for(j=Number(varObj.gridSize);j<len2;j+=Number(varObj.gridSize))
								{									
									lastPt = pt;
									pt = ghost.MathUtil.calLinePoint(lx,ly,x,y,j);
									if(!s._scene.canPass(pt.x,pt.y,canPassFlag))								
									{
										varObj.tempPath.unshift([lastPt.x/varObj.gridSize|0,lastPt.y/varObj.gridSize|0]);
										abort = true;
										break;
									}									
								}								
							}
							col = x / varObj.gridSize|0;
							row = y / varObj.gridSize|0;
							if(!s._scene.canGridPass(col,row,canPassFlag))							
							{
								abort = true;
								break;
							}															
							if(abort)
								break;
							varObj.tempPath.unshift([col,row]);													
						}
						if(abort)
						{
							//有障碍中断
							break;
						}
						//末段寻路，重新初始化
						let startCol2:number,startRow2:number;							
						startRow2 = route.pop()/varObj.gridSize|0;
						startCol2 = route.pop()/varObj.gridSize|0;
						varObj.ndCurrent = varObj.ndStart = ANode.createANode([startCol2,startRow2],startCol2 + startRow2*s._mapWidth);
						varObj.aOpenList = [];							
						varObj.aTryList=[];
						varObj.aCloseList=[];							
						varObj.nCrtTry = 0;							
						varObj.ndEnd = ANode.createANode([endCol,endRow],endCol + endRow*s._mapWidth);
						varObj.aOpenList.push(varObj.ndStart.clone());
						route.length = 0;
					}
					else
					{
						// varObj.apath = s.getPath(varObj.apath, varObj.aCloseList, varObj.ndStart.id);									
						// varObj.ndStart = varObj.ndCurrent;					
						// varObj.apath = varObj.apath.length > 0?varObj.apath:null;
						// if(varObj.apath && varObj.apath.length > 0 && varObj.tempPath && varObj.tempPath.length > 0)
						// 	varObj.apath = varObj.apath.concat(varObj.tempPath);
						break;
					}
				}
				if(thread.isTimeout())
					return;
			}
			if(!abort)
			{
				varObj.apath = s.getPath(varObj.apath, varObj.aCloseList, varObj.ndStart.id);					
				varObj.ndStart = varObj.ndCurrent;
				varObj.apath = varObj.apath.length > 0?varObj.apath:null;
			}
			if(varObj.apath == null || varObj.apath.length == 0)
				varObj.apath = varObj.tempPath;
			else if(varObj.tempPath && varObj.tempPath.length > 0)
				varObj.apath = varObj.apath.concat(varObj.tempPath);
			thread.excEnd(varObj.apath);
		}
		/**搜索路径
		 * @param startCol 起始列索引
		 * @param startRow 起始行索引
		 * @param endCol 结束列索引
		 * @param endRow 结束行索引
		 * @param trackArr 寻路返回的结果数组，不传则创建一个新数组，默认null	 
		 * @param nMaxTry 最大寻路步数限制，默认0 使用系统默认的步数
		 * @param endFlag 结束标志 默认-1，不检测，如果大于0，则检测遍历的格子标志是否符合，符合则直接返回当前路径
		 * @param canPassFlag 寻路中可通行的格子标志，默认Barrier.LAND
		 * @return 如果寻路成功，返回number[][] [[索引x，索引y]……]，失败返回null
		 * */		
		public doSearch(startCol:number,startRow:number,endCol:number,endRow:number,trackArr:number[][]=null,nMaxTry:number=0,endFlag:number=-1,canPassFlag:number=Barrier.LAND):number[][]{
			let s = this;
			let apath:number[][],apos:number[][];	
			let t:number;
			apath = trackArr;
			if(s._debug)			
				t = Date.now();			
			s.clearANodes();			
			s._aTryList.length = 0;
			s._ndCurrent = s._ndStart = ANode.createANode([startCol,startRow],startCol + startRow*s._mapWidth);
			s._ndEnd = ANode.createANode([endCol,endRow],endCol + endRow*s._mapWidth);
			s._aOpenList.push(s._ndStart.clone());
			if(!nMaxTry) nMaxTry = s._nMaxTry;
			while(s._aOpenList.length){
				s._nCrtTry ++ ;
				//如果超出寻路步数限制
				if(s._nCrtTry > nMaxTry){
					s.destroyData();
					return apath;			
				}
				s._aTryList.push(s._ndCurrent);
				apos = s.getRound(s._aCloseList, s._ndStart, s._ndCurrent, s._ndCurrent.pos, endFlag, canPassFlag);
				if(apos == null)
				{
					apath = s.getPath(apath, s._aCloseList, s._ndStart.id);
					s.destroyData();					
					s._ndStart = s._ndCurrent;					
					apath = apath.length > 0?apath:null;
					break;
				}

				s.getF(s._aOpenList, s._ndStart, s._ndCurrent, s._ndEnd, apos);
				//按照F值由大到小的顺序排列开启列表
				s._aOpenList.sort(s.sortF);
				//将开启列表最后一位元素列入关闭列表
				var lastNode:ANode = s._aOpenList[s._aOpenList.length - 1];
				s._aCloseList.push(lastNode);				
				s._ndCurrent = lastNode;
				if(s._aOpenList.length>1)
					s._aOpenList.pop();
				//如果当前节点是目标节点，路径找到，返回true
				if(s._ndCurrent.id == s._ndEnd.id){					
					apath = s.getPath(apath, s._aCloseList, s._ndStart.id);
					s.destroyData();					
					s._ndStart = s._ndCurrent;					
					apath = apath.length > 0?apath:null;
					break;
				}
			}			
			s.destroyData();			
			if(s._debug)
			{
				console.log("本次寻路耗时："+(Date.now() - t)+",步数："+s._aTryList.length);
				s.drawTestPath(apath,s._aTryList);
			}			
			return apath;
		}
		public get tryList():ANode[]
		{
			return this._aTryList;
		}
		//清空各数组
		private destroyData():void{
			let s =this;
			s.clearANodes();
			s._nCrtTry = 0;			
		}
		/**取得路径数组
		 * @param trackArr 寻路返回的结果数组
		*/
		private getPath(trackArr:number[][],aCloseList:ANode[],id:number):number[][]{			
			var apath:number[][] = trackArr?trackArr:[];
    		var tmpnode:ANode = aCloseList[aCloseList.length-1];
			if(tmpnode == null)
				return apath;
			apath.push(tmpnode.pos);
			var inc:number = 0;
			while(inc <= aCloseList.length){
				inc++
				for(var i:number = 0;i<aCloseList.length;i++){
					if(aCloseList[i].id == tmpnode.pid){
						tmpnode = aCloseList[i];
						apath.push(tmpnode.pos)
					}
					if(tmpnode.id == id)
						break;
				}
			}
			apath.pop();
			// if(window["PF_INFO"]["consolePath"]){
			// 	apath = this.floyd(apath);
			// 	console.log("打印修正后的路径:", apath.toString());
			// }
			return apath;
		}
		/** 此方法会修改传入的path */
        private floyd(path: number[][]): number[][] {
            if (path == null) {
                return null;
            }
            let len: number = path.length;
            let i: number;
            if (len > 2) {
                let vector: number[] = [];
                let tempVector: number[] = [];
                this.floydVector(vector, path[len - 1], path[len - 2]);
                for (i = path.length - 3; i >= 0; i--) {
                    let point: number[] = path[i + 1];
                    this.floydVector(tempVector, point, path[i]);
                    if (vector[0] == tempVector[0] && vector[1] == tempVector[1]) {
						path.splice(i + 1, 1);
                    } else {
                        vector[0] = tempVector[0];
                        vector[1] = tempVector[1];
                    }
                }
            }
            len = path.length;
            for (i = len - 1; i >= 0; i--) {
                for (let j: number = 0; j <= i - 2; j++) {
                    if (this.isPassable(path[i], path[j])) {
                        for (let k: number = i - 1; k > j; k--) {
							path.splice(k, 1)
                        }
                        i = j;
                        len = path.length;
                        break;
                    }
                }
            }
            return path;
        }

        private floydVector(target: number[], n1: number[], n2: number[]): void {
            target[0] = n1[0] - n2[0];
            target[1] = n1[1]- n2[1];
        }

		private isPassable(p1: number[], p2: number[]): boolean {
			let x0 = p1[0] * 32;
			let y0 = p1[1] * 32;
			let x1 = p2[0] * 32;
			let y1 = p2[1] * 32;
            return this.isLinePassable(x0, y0, x1, y1);
        }

		private isLinePassable(x0: number, y0: number, x1: number, y1: number): boolean {
            x0 = +x0 | 0;
            y0 = +y0 | 0;
            x1 = +x1 | 0;
            y1 = +y1 | 0;
            let x: number = x0;
            let y: number = y0;

            if (!this._scene.canPass(x0, y0) || !this._scene.canPass(x1, y1)) {
                return false;
            }
            let dx: number = x1 - x0;
            let dy: number = y1 - y0;
            let MaxStep: number = Math.max(Math.abs(dx), Math.abs(dy));

            let stepX: number = dx / MaxStep;
            let stepY: number = dy / MaxStep;

            for (let i: number = 1; i < MaxStep; ++i) {
                x += stepX;
                y += stepY;
                if (!this._scene.canPass(Math.floor(x), Math.floor(y))) {
                    return false;
                }
            }
            return true;
        }

		public dataChange(listenId: number): void
		{
			let s = this;
			if(s._listenId == listenId)
			{
				if(s.testLay)
				{
					s.testLay.x = -s._scene.mapX;
					s.testLay.y = -s._scene.mapY;
				}
			}
		}
		public drawTestPath(arr:number[][],tryList:ANode[]):void
		{
			let i:number,len:number;
			let g:Laya.Graphics;
			let s =this;
			let gridSize:number;
			if(!s._debug)return;
			if(s.testLay == null)
			{
				s.testLay = new GYSprite;
				s.testLay.mouseThrough = true;
				s._scene.sceneLayer.addChild(s.testLay);
				s._listenId = s._scene.mapMoveListener.addListener(s)
			}
			gridSize = s._scene.gridSize;
			g = <Laya.Graphics>s.testLay.graphics;
			g.clear();
			if(arr && arr.length > 0)
			{				
				len = arr.length;
				for(i=0;i<len;++i)
				{					
					g.drawRect(arr[i][0]*gridSize + 1,arr[i][1]*gridSize + 1,gridSize - 2,gridSize - 2, "#ff0000");
				}				
			}
			if(tryList && tryList.length > 0)		
			{				
				len = tryList.length;
				for(i=0;i<len;++i)
				{					
					g.drawRect(tryList[i].pos[0]*gridSize + 4,tryList[i].pos[1]*gridSize + 4,gridSize - 8,gridSize - 8, "#0000ff");
				}				
			}
		}
		private clearANodes():void
		{
			let s =this;
			let len:number;
			if(s._ndStart)
			{
				s._ndStart.clear();
				s._ndStart = null;
			}
			if(s._ndStart)
			{
				s._ndEnd.clear();
				s._ndEnd = null;
			}			
			len = s._aOpenList.length;
			while(--len > -1)
			{
				s._aOpenList[len].clear();
			}
			len = s._aCloseList.length;
			while(--len > -1)
			{
				s._aCloseList[len].clear();
			}
			s._aOpenList.length = 0;
			s._aCloseList.length = 0;			
		}
		public dispose():void
		{
			let s = this;
			if(s.testLay)
				s.testLay.dispose();
			if(s._listenId > -1)
				s._scene.mapMoveListener.removeListener(s);
			s.clearANodes();
			s._aTryList.length = 0;
		}
	}
}